home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 15456 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.6 KB

  1. Path: nntp.teleport.com!usenet
  2. From: GHouck <hksys@teleport.com>
  3. Newsgroups: comp.lang.c
  4. Subject: Re: bubble sort walkthrough needed, please
  5. Date: 19 Apr 1996 04:55:25 GMT
  6. Organization: systems hk
  7. Message-ID: <4l76bt$t4h@nadine.teleport.com>
  8. References: <4l39b4$s2h@coranto.ucs.mun.ca>
  9. NNTP-Posting-Host: ip-pdx20-13.teleport.com
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=us-ascii
  12. Content-Transfer-Encoding: 7bit
  13. X-Mailer: Mozilla 1.22 (Windows; I; 32bit)
  14.  
  15. jdeeley@calvin.stemnet.nf.ca (J.Deeley) wrote:
  16. >
  17. >I am trying to understand how this bubble sort is working. I understand
  18. [snip]
  19. >that I can't fathom. I've been working at this ever since last night and
  20. >I still don't get it. Could someone tell me what is going on in that
  21. >part?
  22. >main ()
  23. >{
  24. >        int item[100];
  25. >        int a, b, t;
  26. >        int count;
  27. >        
  28. >        /* read in numbers */
  29. >        printf("How many numbers? ");
  30. >        scanf("%d", &count);
  31. >        for (a=0; a<count; a++) scanf("%d", &item[a]);
  32. >        
  33. >        /* now sort them using a bubble sort */
  34. >        for(a=1; a<count; a++)
  35. >                for(b=count-1; b>=a;--b) {
  36. >                        /* compare the adjacent elements */
  37. >                                if(item [b-1] > item [b]) {
  38. >                                        /* exchange elements */
  39. >                                        t = item [b-1];
  40. >                                        item[b-1] = item [b];
  41. >                                        item [b] = t;
  42. >                                        }
  43. >                                }
  44. >                                
  45. JD
  46. It doesn't look exactly like the one I am vaguely familiar with, however, it
  47. appears to be doing this:
  48.  
  49.   1. The outer (a) loop provides the inner (b) loop with an ending value, starting
  50.      at 1, incrementing to the (count-1).
  51.   2. The inner loop then sequences backward from the end of the array,
  52.      comparing (and swapping) adjacent elements if they are not in ascending order.
  53.   3. The inner loop completes when the value of (b) is less than the value of (a).
  54.   4. The outer (a) loop then increments, reducing the range that the inner (b) has
  55.      to iterate.
  56.  
  57. This is supposed to float (bubble) the smaller values to the top; however, I have
  58. always seen it with the inner loop index increasing rather than decreasing in value.  The
  59. bubble sort, once you figure it out, is handy for small, quick and dirty sorts, where
  60. the effort to implement something more complex (and perhaps more efficient) is just not
  61. worth it.  Once you get over a score of elements in the array, the n^2 time it takes starts
  62. to become prohibitive.
  63.  
  64. Yours,
  65.  
  66. Geoff Houck
  67. systems hk
  68.  
  69.  
  70.  
  71.